/**
 * 
 */
package com.module.bp.bus.graph;

import java.util.Iterator;
import java.util.Stack;

import com.module.bp.bus.BPGlobals;

/**
 * @author Donald
 *
 */
public final class BreadthFirstSearch {
	/** the value of infinity. */
	private static final int INFINITY = Integer.MAX_VALUE;
	/** the list of marked vertices. marked[v] = is there an s-v path. */
    private boolean[] marked;
    /** edgeTo[v] = previous edge on shortest s-v path. */
    private int[] edgeTo;
    /** distTo[v] = number of edges shortest s-v path. */
    private int[] distTo;
	/** the list of marked vertices. marked[v] = is there an s-v path. */
    private boolean[] markedRiver;
    /** edgeTo[v] = previous edge on shortest s-v path. */
    private int[] edgeToRiver;
    /** distTo[v] = number of edges shortest s-v path. */
    private int[] distToRiver;
    /**
     * Creates a new instance of {@link BreadthFirstSearch} associated with a 
     * single source vertex.
     * @param graph the graph being searched
     * @param source the source vertex
     */
    public BreadthFirstSearch(final SimpleGraph graph, final int source) {
        marked = new boolean[graph.getNumVertices()];
        distTo = new int[graph.getNumVertices()];
        edgeTo = new int[graph.getNumVertices()];
        markedRiver = new boolean[graph.getNumVertices()];
        distToRiver = new int[graph.getNumVertices()];
        edgeToRiver = new int[graph.getNumVertices()];
        search(graph, source);
        searchRiverPaths(graph, source);

        // assert check(graph, source);
    }
    /**
     * Performs a breadth-first search from a single source.
     * @param graph the graph being searched
     * @param source the source vertex
     */
    private void search(final SimpleGraph graph, final int source) {
        Queue<Integer> queue = new Queue<Integer>();
        for (int vertex = 0; vertex < graph.getNumVertices(); vertex++) {
        	distTo[vertex] = INFINITY;
        }
        distTo[source] = 0;
        marked[source] = true;
        queue.enqueue(source);
        while (!queue.isEmpty()) {
            int vertex = queue.dequeue();
            Iterator<Integer> iter = 
            	graph.getImmediateAdjacencies(vertex).iterator();
            while (iter.hasNext()) {
            	Integer nextVertex = iter.next();
            	if (distTo[vertex] + 1 > 8) {
            		continue;
            	} else if (!marked[nextVertex]) {
                	// next vertex hasn't been visited yet, mark it down
	                edgeTo[nextVertex] = vertex;
	                distTo[nextVertex] = distTo[vertex] + 1;
	                marked[nextVertex] = true;
	                queue.enqueue(nextVertex);
                } else if (distTo[nextVertex] == distTo[vertex] + 1) {
                	//is the matching path a river path?
                	// go through the path, checking for river nodes
                	int back = vertex;
                	boolean foundRiver = false;
                	while (back != source) {
                		if (back >= BPGlobals.MAP_NUM_HEXES) {
                			foundRiver = true;
                			break;
                		}
                		back = edgeTo[back];
                	}
                	if (foundRiver) {
                		edgeTo[nextVertex] = vertex;
    	                distTo[nextVertex] = distTo[vertex] + 1;
    	                marked[nextVertex] = true;
    	                queue.enqueue(nextVertex);
                	}
                }
            }
        }
    }
    /**
     * Performs a breadth-first search from a single source.
     * @param graph the graph being searched
     * @param source the source vertex
     */
    private void searchRiverPaths(final SimpleGraph graph, final int source) {
        Queue<Integer> queue = new Queue<Integer>();
        for (int vertex = 0; vertex < graph.getNumVertices(); vertex++) {
        	distToRiver[vertex] = INFINITY;
        }
        distToRiver[source] = 0;
        markedRiver[source] = true;
        queue.enqueue(source);
        while (!queue.isEmpty()) {
            int vertex = queue.dequeue();
            Iterator<WeightedEdge> iterEdge = 
            	graph.getEdges(vertex).iterator();
            if (vertex == source) {
            	// from source, only mark down vertices that are river nodes
                while (iterEdge.hasNext()) {
                	WeightedEdge edge = iterEdge.next();
                	if (edge.getWeight() 
                			== BPGlobals.GRAPH_LAND_TO_RIVER_WEIGHT) {
                		// allowed edge. mark down the next vertex
                    	Integer nextVertex = edge.getTo();
                    	// next vertex hasn't been visited yet, mark it down
                        if (!markedRiver[nextVertex]) {
        	                edgeToRiver[nextVertex] = vertex;
        	                distToRiver[nextVertex] = distToRiver[vertex] + 1;
        	                markedRiver[nextVertex] = true;
        	                queue.enqueue(nextVertex);
                        }
                	}
                }
            } else {
            	// from river node, only enqueue river nodes
                while (iterEdge.hasNext()) {
                	WeightedEdge edge = iterEdge.next();
                	if (edge.getWeight() 
                			== BPGlobals.GRAPH_RIVER_TO_LAND_WEIGHT) {
                		// moving from river to land.
                		// mark this node, but don't enqueue
                    	Integer nextVertex = edge.getTo();
                    	// next vertex hasn't been visited yet, mark it down
                        if (!markedRiver[nextVertex]) {
                        	edgeToRiver[nextVertex] = vertex;
        	                distToRiver[nextVertex] = distToRiver[vertex] + 1;
        	                markedRiver[nextVertex] = true;
                        }
                	} else {
                    	// moving from river to river.
                		// mark this node and enqueue
                		Integer nextVertex = edge.getTo();
                    	// next vertex hasn't been visited yet, mark it down
                        if (!markedRiver[nextVertex]) {
        	                edgeToRiver[nextVertex] = vertex;
        	                distToRiver[nextVertex] = distToRiver[vertex] + 1;
        	                markedRiver[nextVertex] = true;
        	                queue.enqueue(nextVertex);
                        }
                	}
                }
            }
        }
    }
    /**
     * Determines if there is a path to a specific vertex.
     * @param vertex the vertex being searched for
     * @return true if there is a path to a specific vertex; false otherwise
     */
    public boolean hasPathTo(final int vertex) {
        return marked[vertex];
    }
    /**
     * Determines if there is a river path to a specific vertex.
     * @param vertex the vertex being searched for
     * @return true if there is a path to a specific vertex; false otherwise
     */
    public boolean hasRiverPathTo(final int vertex) {
        return markedRiver[vertex];
    }
    /**
     * Finds the length of the shortest path between the source and a specific 
     * vertex.
     * @param vertex the vertex being searched for
     * @return <code>int</code>
     */
    public int distanceTo(final int vertex) {
        return distTo[vertex];
    }
    /**
     * Finds the length of the shortest river path between the source and a 
     * specific vertex.
     * @param vertex the vertex being searched for
     * @return <code>int</code>
     */
    public int riverDistanceTo(final int vertex) {
        return distToRiver[vertex];
    }
    /**
     * Gets the shortest river path between the source and a specific vertex.
     * @param vertex the vertex being searched for
	 * @return {@link Iterable}&lt;{@link Integer}&gt;; or null if no path was 
	 * found
     */
    public Iterable<Integer> riverPathTo(final int vertex) {
        if (!hasRiverPathTo(vertex)) {
        	return null;
        }
        Stack<Integer> path = new Stack<Integer>();
        int x;
        for (x = vertex; distToRiver[x] != 0; x = edgeToRiver[x]) {
        	path.push(x);
        }
        path.push(x);
        return path;
    }
    /**
     * Gets the shortest path between the source and a specific vertex.
     * @param vertex the vertex being searched for
	 * @return {@link Iterable}&lt;{@link Integer}&gt;; or null if no path was 
	 * found
     */
    public Iterable<Integer> pathTo(final int vertex) {
        if (!hasPathTo(vertex)) {
        	return null;
        }
        Stack<Integer> path = new Stack<Integer>();
        int x;
        for (x = vertex; distTo[x] != 0; x = edgeTo[x]) {
        	path.push(x);
        }
        path.push(x);
        return path;
    }
    // check optimality conditions for single source
    private boolean check(final SimpleGraph G, final int s) {
        // check that the distance of s = 0
        if (distTo[s] != 0) {
            return false;
        }

        // check that for each edge v-w dist[w] <= dist[v] + 1
        // provided v is reachable from s
        for (int v = 0; v < G.getNumVertices(); v++) {
            for (int w : G.getImmediateAdjacencies(v)) {
                if (hasPathTo(v) != hasPathTo(w)) {
                	return false;
                }
                if (hasPathTo(v) && (distTo[w] > distTo[v] + 1)) {
                    return false;
                }
            }
        }

        // check that v = edgeTo[w] satisfies distTo[w] + distTo[v] + 1
        // provided v is reachable from s
        for (int w = 0; w < G.getNumVertices(); w++) {
            if (!hasPathTo(w) || w == s) continue;
            int v = edgeTo[w];
            if (distTo[w] != distTo[v] + 1) {
                return false;
            }
        }

        return true;
    }
}
